import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**马踏棋盘算法：骑士周游问题
 *  图的深度优先搜索（DFS）的应用
 *
 */

public class HorseChessBoard {

    private static int X;//棋盘的列数
    private static int Y;//棋盘的行数
    private static boolean visited[];
    private static boolean finished;

    public static void main(String[] args) {
        System.out.println("骑士周游运算开始---");
        X=8;
        Y=8;
        int row =1;
        int column =1;
        int[][]chessboard= new int[X][Y];
        visited = new boolean[X*Y];

        traversalChessBoard(chessboard,row-1,column-1,1);

        for (int[] rows: chessboard) {
            for (int step: rows) {
                System.out.print(step+"\t");
            }
            System.out.println();
        }
    }

    /**
     * 完成骑士周游的算法
     * @param chessboard 棋盘
     * @param row  行位置，从0开始
     * @param column 列位置，从0开始
     * @param step: 第几步，起始位置为第一步
     */
    private static void traversalChessBoard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        visited[row*8+column] = true;//访问了
        //获取下一个可以走的位置
        ArrayList<Point> ps = next(new Point(column,row));
        sort(ps);

        while (!ps.isEmpty()){
            Point p = ps.remove(0);
            if (!visited[p.y*X+p.x]){
                traversalChessBoard(chessboard,p.y,p.x,step+1);
            }
        }

        if (step<X*Y && !finished){
            chessboard[row][column] =0;
            visited[row*X+column] = false;
        }else {
            finished = true;
        }


    }



    /**
     * 根据当前位置计算下一步能走哪些位置，并放入集合中
     * @param curPoint
     * @return
     */

    public static ArrayList<Point> next(Point curPoint){
        ArrayList<Point> ps = new ArrayList<Point>();
        Point p1 = new Point();
        if ((p1.x = curPoint.x-2)>=0&&(p1.y= curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x-1)>=0&&(p1.y= curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x+1)<X&&(p1.y= curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x+2)<X &&(p1.y= curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x+2)<X &&(p1.y= curPoint.y+1)<Y){
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x+1)<X &&(p1.y= curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x-1)>=0 &&(p1.y= curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x-2)>=0 &&(p1.y= curPoint.y+1)<Y){
            ps.add(new Point(p1));
        }
        return ps;
    }

    //排序：减少回溯次数
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1<count2){
                    return -1;
                }else if (count1==count2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}
